// 版权所有2010 Go作者。保留所有权利。
// 此源代码的使用受BSD样式
// 许可证的约束，该许可证可以在许可证文件中找到。

// 此文件实现多精度有理数。

package big

import (
	"fmt"
	"math"
)

// Rat代表任意精度的商A/b。
// 老鼠的零值代表0。
// 
// 操作总是采用指针参数（*Rat）而不是Rat值，每个唯一的Rat值都需要
// 它自己唯一的*Rat指针。要“复制”Rat值，必须将现有（或新分配的）Rat设置为
// 使用Rat的新值。集合方法；不支持Rats的浅拷贝
// 并可能导致错误。
type Rat struct {
	// 要在没有初始化的情况下为Rat工作创建零值，
	// b（len（b）=0）的零值的作用类似于b==1。在
	// 最早的机会（当分配给Rat 
	// 时），此类未初始化的分母设置为1。
	// a.neg决定大鼠的体征，b.neg被忽略。
	a, b Int
}

// NewRat创建一个带有分子a和分母b的新Rat。
func NewRat(a, b int64) *Rat {
	return new(Rat).SetFrac64(a, b)
}

// SetFloat64将z精确设置为f并返回z。
// 如果f不是有限的，SetFloat返回零。
func (z *Rat) SetFloat64(f float64) *Rat {
	const expMask = 1<<11 - 1
	bits := math.Float64bits(f)
	mantissa := bits & (1<<52 - 1)
	exp := int((bits >> 52) & expMask)
	switch exp {
	case expMask: // 非有限
		return nil
	case 0: // 非规范
		exp -= 1022
	default: // 正常
		mantissa |= 1 << 52
		exp -= 1023
	}

	shift := 52 - exp

	// 优化（？）部分预正常化。
	for mantissa&1 == 0 && shift > 0 {
		mantissa >>= 1
		shift--
	}

	z.a.SetUint64(mantissa)
	z.a.neg = f < 0
	z.b.Set(intOne)
	if shift > 0 {
		z.b.Lsh(&z.b, uint(shift))
	} else {
		z.a.Lsh(&z.a, uint(-shift))
	}
	return z.norm()
}

// quotToFloat32返回最接近商a/b的非负浮点值
// 在
// 中间情况下使用舍入到偶数。它不会改变自己的论点。
// 前提条件：b为非零；a和b没有共同的因素。
func quotToFloat32(a, b nat) (f float32, exact bool) {
	const (
		// 以位表示的浮点大小
		Fsize = 32

		// 尾数
		Msize  = 23
		Msize1 = Msize + 1 // 包括隐式1 
		Msize2 = Msize1 + 1

		// 指数
		Esize = Fsize - Msize1
		Ebias = 1<<(Esize-1) - 1
		Emin  = 1 - Ebias
		Emax  = Ebias
	)

	// TODO（adonovan）：专门化常见的退化情况：1.0，整数。
	alen := a.bitLen()
	if alen == 0 {
		return 0, true
	}
	blen := b.bitLen()
	if blen == 0 {
		panic("division by zero")
	}

	// 1。左移A或B，使商A/B位于[1<<Msize1，1<<（Msize2+1）
	// （如果A<B，则为Msize2位；如果A>=B，则为Msize2+1位）。
	// 这比Msize的float32尾数字段宽度大2或3：
	// -可选的额外位在下面的第3步中移位。
	// -在“正常”代表；
	// /-四舍五入期间将使用低阶1，然后丢弃。
	exp := alen - blen
	var a2, b2 nat
	a2 = a2.set(a)
	b2 = b2.set(b)
	if shift := Msize2 - exp; shift > 0 {
		a2 = a2.shl(a2, uint(shift))
	} else if shift < 0 {
		b2 = b2.shl(b2, uint(-shift))
	}

	// 2。计算商和余数（q，r）。注意：由于
	// 额外移位，q的低位逻辑上是r的高位。
	var q nat
	q, r := q.div(a2, a2, b2) // （循环a2）
	mantissa := low32(q)
	haveRem := len(r) > 0 // 尾数和1&&！haveRem=>余数正好是

	// 3的一半。如果商不适合Msize2位，则重新按b2除法（实际上——我们是以增量方式完成的）。
	if mantissa>>Msize2 == 1 {
		if mantissa&1 == 1 {
			haveRem = true
		}
		mantissa >>= 1
		exp++
	}
	if mantissa>>Msize1 != 1 {
		panic(fmt.Sprintf("expected exactly %d bits of result", Msize2))
	}

	// 4。四舍五入。
	if Emin-Msize <= exp && exp <= Emin {
		// 非规范病例；失去“移位”精度。
		shift := uint(Emin - (exp - 1)) // [1..Esize1）
		lostbits := mantissa & (1<<shift - 1)
		haveRem = haveRem || lostbits != 0
		mantissa >>= shift
		exp = 2 - Ebias // /==exp+shift 
	}
	// Round q使用四舍五入到偶数。
	exact = !haveRem
	if mantissa&1 != 0 {
		exact = false
		if haveRem || mantissa&2 != 0 {
			if mantissa++; mantissa >= 1<<Msize2 {
				// 完成翻转11…1=>100…0，所以shift是安全的
				mantissa >>= 1
				exp++
			}
		}
	}
	mantissa >>= 1 // 放弃舍入位。尾数现在按1缩放。

	f = float32(math.Ldexp(float64(mantissa), exp-Msize1))
	if math.IsInf(float64(f), 0) {
		exact = false
	}
	return
}

// quotToFloat64返回最接近商a/b的非负浮点值
// 使用舍入到ev在
// /案例中为en。它不会改变自己的论点。
// 前提条件：b为非零；a和b没有共同的因素。
func quotToFloat64(a, b nat) (f float64, exact bool) {
	const (
		// 浮点大小以位为单位
		Fsize = 64

		// 尾数
		Msize  = 52
		Msize1 = Msize + 1 // 包括隐式1 
		Msize2 = Msize1 + 1

		// 指数
		Esize = Fsize - Msize1
		Ebias = 1<<(Esize-1) - 1
		Emin  = 1 - Ebias
		Emax  = Ebias
	)

	// TODO（adonovan）：专门化常见的退化情况：1.0，整数。
	alen := a.bitLen()
	if alen == 0 {
		return 0, true
	}
	blen := b.bitLen()
	if blen == 0 {
		panic("division by zero")
	}

	// 1。左移A或B，使商A/B位于[1<<Msize1，1<<（Msize2+1）
	// （如果A<B，则为Msize2位；如果A>=B，则为Msize2+1位）。
	// 这比Msize的float64尾数字段宽度大2或3：
	// -可选的额外位在下面的第3步中移位。
	// -在“正常”代表；
	// /-四舍五入期间将使用低阶1，然后丢弃。
	exp := alen - blen
	var a2, b2 nat
	a2 = a2.set(a)
	b2 = b2.set(b)
	if shift := Msize2 - exp; shift > 0 {
		a2 = a2.shl(a2, uint(shift))
	} else if shift < 0 {
		b2 = b2.shl(b2, uint(-shift))
	}

	// 2。计算商和余数（q，r）。注意：由于
	// 额外移位，q的低位逻辑上是r的高位。
	var q nat
	q, r := q.div(a2, a2, b2) // （循环a2）
	mantissa := low64(q)
	haveRem := len(r) > 0 // 尾数和1&&！haveRem=>余数正好是

	// 3的一半。如果商不适合Msize2位，则重新按b2除法（实际上——我们以增量方式完成）。
	if mantissa>>Msize2 == 1 {
		if mantissa&1 == 1 {
			haveRem = true
		}
		mantissa >>= 1
		exp++
	}
	if mantissa>>Msize1 != 1 {
		panic(fmt.Sprintf("expected exactly %d bits of result", Msize2))
	}

	//    4. 四舍五入。
	if Emin-Msize <= exp && exp <= Emin {
		// 非规范病例；失去“移位”精度。
		shift := uint(Emin - (exp - 1)) // [1..Esize1）
		lostbits := mantissa & (1<<shift - 1)
		haveRem = haveRem || lostbits != 0
		mantissa >>= shift
		exp = 2 - Ebias // /==exp+shift 
	}
	// 使用半舍五入到偶数的方法对q进行四舍五入。
	exact = !haveRem
	if mantissa&1 != 0 {
		exact = false
		if haveRem || mantissa&2 != 0 {
			if mantissa++; mantissa >= 1<<Msize2 {
				// 完成翻转11…1=>100…0，所以shift是安全的
				mantissa >>= 1
				exp++
			}
		}
	}
	mantissa >>= 1 // 放弃舍入位。尾数现在按1缩放。

	f = math.Ldexp(float64(mantissa), exp-Msize1)
	if math.IsInf(f, 0) {
		exact = false
	}
	return
}

// Float32返回x的最接近的Float32值和一个bool，指示
// f是否代表xy、 如果x的大小太大，以至于不能用浮点数32来表示，那么f是无穷大，而exact是假的。
// 即使f==0，f的符号始终与x的符号匹配。
func (x *Rat) Float32() (f float32, exact bool) {
	b := x.b.abs
	if len(b) == 0 {
		b = natOne
	}
	f, exact = quotToFloat32(x.a.abs, b)
	if x.a.neg {
		f = -f
	}
	return
}

// Float64返回x的最接近的Float64值，并返回一个bool，指示
// f是否精确表示x。如果x的大小太大，以至于不能用浮点数64来表示，那么f是无穷大，而exact是假的。
// 即使f==0，f的符号始终与x的符号匹配。
func (x *Rat) Float64() (f float64, exact bool) {
	b := x.b.abs
	if len(b) == 0 {
		b = natOne
	}
	f, exact = quotToFloat64(x.a.abs, b)
	if x.a.neg {
		f = -f
	}
	return
}

// SetFrac将z设置为a/b并返回z。
// 如果b==0，SetFrac恐慌。
func (z *Rat) SetFrac(a, b *Int) *Rat {
	z.a.neg = a.neg != b.neg
	babs := b.abs
	if len(babs) == 0 {
		panic("division by zero")
	}
	if &z.a == b || alias(z.a.abs, babs) {
		babs = nat(nil).set(babs) // 复制
	}
	z.a.abs = z.a.abs.set(a.abs)
	z.b.abs = z.b.abs.set(babs)
	return z.norm()
}

// SetFrac64将z设置为a/b并返回z。
// 如果b==0，SetFrac64将崩溃。
func (z *Rat) SetFrac64(a, b int64) *Rat {
	if b == 0 {
		panic("division by zero")
	}
	z.a.SetInt64(a)
	if b < 0 {
		b = -b
		z.a.neg = !z.a.neg
	}
	z.b.abs = z.b.abs.setUint64(uint64(b))
	return z.norm()
}

// SetInt将z设置为x（通过复制x）并返回z。
func (z *Rat) SetInt(x *Int) *Rat {
	z.a.Set(x)
	z.b.abs = z.b.abs.setWord(1)
	return z
}

// SetInt64将z设置为x并返回z。
func (z *Rat) SetInt64(x int64) *Rat {
	z.a.SetInt64(x)
	z.b.abs = z.b.abs.setWord(1)
	return z
}

// SetUint64将z设置为x并返回z。
func (z *Rat) SetUint64(x uint64) *Rat {
	z.a.SetUint64(x)
	z.b.abs = z.b.abs.setWord(1)
	return z
}

// Set z设置为x（通过复制x）并返回z。
func (z *Rat) Set(x *Rat) *Rat {
	if z != x {
		z.a.Set(&x.a)
		z.b.Set(&x.b)
	}
	if len(z.b.abs) == 0 {
		z.b.abs = z.b.abs.setWord(1)
	}
	return z
}

func (z *Rat) Abs(x *Rat) *Rat {
	z.Set(x)
	z.a.neg = false
	return z
}

// Neg将z设置为-x并返回z。
func (z *Rat) Neg(x *Rat) *Rat {
	z.Set(x)
	z.a.neg = len(z.a.abs) > 0 && !z.a.neg // 0没有符号
	return z
}

// Inv将z设置为1/x并返回z。
// 如果x==0，Inv恐慌。
func (z *Rat) Inv(x *Rat) *Rat {
	if len(x.a.abs) == 0 {
		panic("division by zero")
	}
	z.Set(x)
	z.a.abs, z.b.abs = z.b.abs, z.a.abs
	return z
}

// 符号返回：
// 
// /-1如果x<0 
// 0如果x==0 
// /+1如果x>0 
// 
func (x *Rat) Sign() int {
	return x.a.Sign()
}

// IsInt报告x的分母是否为1。
func (x *Rat) IsInt() bool {
	return len(x.b.abs) == 0 || x.b.abs.cmp(natOne) == 0
}

// Num返回x的分子；它可能小于等于0。
// 结果是对x分子的引用；
// 如果将新值指定给x，则可能会发生变化，反之亦然。
// 分子的符号对应于x的符号。
func (x *Rat) Num() *Int {
	return &x.a
}

// Denom返回x的分母；它总是>0。
// 结果是对x分母的引用，除非
// x是未初始化（零值）的Rat，在这种情况下，
// 结果是值为1的新整数。（要初始化x，
// 设置x的任何操作都可以，包括x.Set（x）。）
// 如果结果是对x的分母的引用，那么如果给x分配了一个新值，它可能会改变，反之亦然。
func (x *Rat) Denom() *Int {
	// 注意，x.b.neg被保证为false。
	if len(x.b.abs) == 0 {
		// 注意：如果这被证明是有问题的，我们可以用恐慌代替，并要求Rat对
		// 进行显式初始化。
		return &Int{abs: nat{1}}
	}
	return &x.b
}

func (z *Rat) norm() *Rat {
	switch {
	case len(z.a.abs) == 0:
		// z==0；规范化符号和分母
		z.a.neg = false
		fallthrough
	case len(z.b.abs) == 0:
		// z为整数；规范化分母
		z.b.abs = z.b.abs.setWord(1)
	default:
		// z为分数；规范化分子和分母
		neg := z.a.neg
		z.a.neg = false
		z.b.neg = false
		if f := NewInt(0).lehmerGCD(nil, nil, &z.a, &z.b); f.Cmp(intOne) != 0 {
			z.a.abs, _ = z.a.abs.div(nil, z.a.abs, f.abs)
			z.b.abs, _ = z.b.abs.div(nil, z.b.abs, f.abs)
		}
		z.a.neg = neg
	}
	return z
}

// mulDenom将z设置为分母乘积x*y（通过考虑
// 考虑到x或y的0值必须解释为1）和
// 返回z。
func mulDenom(z, x, y nat) nat {
	switch {
	case len(x) == 0 && len(y) == 0:
		return z.setWord(1)
	case len(x) == 0:
		return z.set(y)
	case len(y) == 0:
		return z.set(x)
	}
	return z.mul(x, y)
}

// scaleDenom将z设置为乘积x*f。
// 如果f==0（分母的零值），z被设置为（x的副本）。如果x==y 
func (z *Int) scaleDenom(x *Int, f nat) {
	if len(f) == 0 {
		z.Set(x)
		return
	}
	z.abs = z.abs.mul(x.abs, f)
	z.neg = x.neg
}

// Cmp比较x和y并返回：
// 
// /-1如果x<y 
// 0如果x==y 
// /+1如果x>y 
// 
func (x *Rat) Cmp(y *Rat) int {
	var a, b Int
	a.scaleDenom(&x.a, y.b.abs)
	b.scaleDenom(&y.a, x.b.abs)
	return a.Cmp(&b)
}

// 将集合z添加到x+y的和，并返回z。
func (z *Rat) Add(x, y *Rat) *Rat {
	var a1, a2 Int
	a1.scaleDenom(&x.a, y.b.abs)
	a2.scaleDenom(&y.a, x.b.abs)
	z.a.Add(&a1, &a2)
	z.b.abs = mulDenom(z.b.abs, x.b.abs, y.b.abs)
	return z.norm()
}

func (z *Rat) Sub(x, y *Rat) *Rat {
	var a1, a2 Int
	a1.scaleDenom(&x.a, y.b.abs)
	a2.scaleDenom(&y.a, x.b.abs)
	z.a.Sub(&a1, &a2)
	z.b.abs = mulDenom(z.b.abs, x.b.abs, y.b.abs)
	return z.norm()
}

func (z *Rat) Mul(x, y *Rat) *Rat {
	if x == y {
		// 一个平方老鼠是正的，不能被减少（无需调用norm（））
		z.a.neg = false
		z.a.abs = z.a.abs.sqr(x.a.abs)
		if len(x.b.abs) == 0 {
			z.b.abs = z.b.abs.setWord(1)
		} else {
			z.b.abs = z.b.abs.sqr(x.b.abs)
		}
		return z
	}
	z.a.Mul(&x.a, &y.a)
	z.b.abs = mulDenom(z.b.abs, x.b.abs, y.b.abs)
	return z.norm()
}

// Quo将z设置为商x/y并返回z.
// 如果y==0，Quo恐慌。
func (z *Rat) Quo(x, y *Rat) *Rat {
	if len(y.a.abs) == 0 {
		panic("division by zero")
	}
	var a, b Int
	a.scaleDenom(&x.a, y.b.abs)
	b.scaleDenom(&y.a, x.b.abs)
	z.a.abs = a.abs
	z.b.abs = b.abs
	z.a.neg = a.neg != b.neg
	return z.norm()
}
